// 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

// 思路，通过kmp算法构建字符串的前缀表，判断字符串长度是否可以被最小重复子串整除
// 时间复杂度：O(n)，n是字符串的长度
// 空间复杂度：O(n)，next数组的大小

function getNext(str) {
    let left = 0
    let right = 1
    let next = new Array(str.length).fill(0)
    while (right < str.length) {
        while (left > 0 && str[left] !== str[right]) {
            left = next[left - 1]
        }
        if (str[left] === str[right]) {
            left++
        }
        next[right] = left
        right++
    }
    return next
}

function repeatedSubstringPattern(str) {
    if (!str.length) {
        return false
    }
    let next = getNext(str)
    let prefixLen = next[str.length - 1]
    if (prefixLen === 0) {
        return false
    }
    return str.length % (str.length - prefixLen) === 0
}

let str = 'ababababab'

console.log(repeatedSubstringPattern(str))